// 基本思想：将未排序数组分到若干桶中，每个桶的元素再进行单独排序
// 步骤： 1. 根据原始数组的值域范围，将数组划分为k个相同大小的子区间，每个区间称为一个桶
// 2. 遍历原始数组元素，将每个元素装入对应区间的桶中
// 3. 对每个桶内的元素单独排序
// 4. 最后按照区间顺序将桶内的元素合并起来

// 时间复杂度： 趋近于O(n)
// 空间复杂度：O(n + m)
// 排序稳定性：如果桶内使用插入排序等稳定排序算法，则桶排序也是一种稳定排序算法

function insertionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let temp = arr[i]
        let j = i
        while (j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1]
            j -= 1
        }
        arr[j] = temp
    }
    return arr
}

function bucketSort(arr, bucket_size = 5) {
    // 1. 计算待排序序列中最大值元素arr_max和最小值元素arr_min
    let arr_max = Math.max(...arr)
    let arr_min = Math.min(...arr)
    // 2. 定义桶的个数
    let bucket_count = Math.floor((arr_max - arr_min) / bucket_size) + 1
    // 3. 定义桶数组buckets
    let buckets = new Array(bucket_count).fill(0).map(_ => [])
    for (let i = 0; i < arr.length; i++) {
        let index = Math.floor((arr[i] - arr_min) / bucket_size)
        buckets[index].push(arr[i])
    }

    // 4. 对每个桶内的元素单独排序，并合并到res数组中
    let res = []
    for (let i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i])
        res.push(...buckets[i])
    }
    return res
}

let arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
console.log(bucketSort(arr));